Radio frequency identification is a technique for storing and recovering remote data by using markers called radio tags (one also speaks of “RFID tags”). A radio tag is a small object, such as a self-adhesive tag, which may be stuck onto, or incorporated into, objects or products. It comprises an antenna associated with an electronic chip which allows it to receive and to respond to radio requests emitted from an emitter-receiver called a reader. Radio tags are used for example to identify persons when the tags are integrated into passports, into transport tickets, or into payment cards, or to identify products such as with a bar code. The reader is then the verifier in charge of the authentication of the tags which are entities to be authenticated.
With a view to protecting privacy, notably the privacy of persons who possess owners of a radio tag, it is generally desirable that the protocol for authenticating tags by a reader possesses three properties:                the protocol must be anonymous, that is to say it must not be possible for a malicious adversary to identify an entity which is involved in an authentication,        the entity must not be traceable, that is to say it must not be possible to link two different authentications of one and the same entity, and        if the malicious adversary obtains the identifier of an entity by any procedure whatsoever, by a so-called “reverse engineering” procedure, by a physical attack on a backing card supporting the tag, etc., it must not be possible to recognize earlier authentications of the entity. The latter property is the so-called “forward privacy” property. It is noted that the anonymity property is an indispensable prerequisite for the fulfillment of the non-traceability and “forward privacy” properties.        
When such a protocol is used for the identification of persons, it is understood that these three properties contribute toward maintaining the privacy of such persons.
In order to satisfy these properties, various authentication protocols may be defined, for example, protocols based on a question-answer mechanism and using a random number. Protocols based on secret-key cryptography are thus known.
In an exemplary use of secret-key cryptography, each entity able to authenticate itself with a verifier possesses a unique secret key, known to the verifier. The “WSRE” protocol (from the name of their authors, Weis-Sarma-Rivest-Engel) is thus known, in which, on a verifier authentication request, the entity uses an identifier ID which is specific to it and computes H(ID∥r) by applying a hash function H to the concatenation of its identifier ID and of a random number r chosen by the entity, and then sends the result of this computation as well as the random number r to the verifier. It is noted that the identifier ID of the entity is used as secret key of the entity. In order that this authentication protocol be anonymous, the verifier must then test each entity identifier, accessible for example via a database of the identifiers, and compute the hash of each of the identifiers concatenated with the random number received so as to retrieve the identifier of the entity which has responded to this authentication request. It will be noted that when the number of entities able to authenticate themselves with the verifier is very large, such a search is very expensive in terms of computations.
In a variant embodiment of such a protocol which avoids a replay by an adversary, the verifier sends a first random number to the entity. The entity responds by returning the concatenate of its identifier with the first random number and with a second random number that it generates, as well as the second random number. In this embodiment also, to guarantee anonymity, a search among all the entity identifiers must be performed, this once again being expensive in terms of computations.
There therefore exists a requirement for a protocol for authenticating an entity with a verifier, which is anonymous and which offers good performance in terms of speediness of authentication.